<?PHP
#
#   FILE:  SearchFacetUI_Base.php
#
#   Part of the Collection Workflow Integration System (CWIS)
#   Copyright 2015-2021 Edward Almasy and Internet Scout Research Group
#   http://scout.wisc.edu/cwis/
#
# @scout:phpstan

namespace Metavus;

use Exception;
use ScoutLib\SearchParameterSet;

/**
 * SearchFacetUI supports the generation of a user interface for faceted
 * search, by taking the search parameters and search results and generating
 * the data needed to lay out the HTML.This is the UI-independent facet
 * generating portion; HTML should be generated by a SearchFacetUI that
 * extends this class.
 */
class SearchFacetUI_Base
{
    # ---- PUBLIC INTERFACE --------------------------------------------------

    /**
     * Constructor, that accepts the search parameters and results and
     *   prepares the facet UI data to be retrieved.
     * @param SearchParameterSet $SearchParams Current search parameter set.
     * @param array $SearchResults Search results as an array where keys give
     *   ItemIds and values give search scores (so the same format SearchEngine
     *   uses to return per-schema results)
     */
    public function __construct(
        SearchParameterSet $SearchParams,
        array $SearchResults
    ) {
        $this->BaseLink = "index.php?P=SearchResults";
        $this->SearchParams = $SearchParams;
        $this->SearchResults = $SearchResults;
        $this->MaxFacetsPerField =
                SystemConfiguration::getInstance()->getInt("MaxFacetsPerField");
        $this->User = User::getCurrentUser();

        $this->ShowCounts = count($SearchResults) <= SearchEngine::numResourcesForFacets();

        $SchemaIds = array_unique(
            Record::getSchemasForRecords(array_keys($SearchResults))
        );

        if (count($SchemaIds) > 1) {
            throw new Exception(
                "SearchFacetUI cannot generate facets for "
                ."multiple schemas at a time."
            );
        }

        $this->SchemaId = reset($SchemaIds);
    }

    /**
     * Get/set the user used for permission checks when generating search
     *   facets.If no user is explicitly set, it defaults to User::getCurrentUser().
     * @param User $NewValue User value to set (OPTIONAL)
     * @return User Current value.
     */
    public function user(User $NewValue = null): User
    {
        if (!is_null($NewValue)) {
            $this->User = $NewValue;
        }

        return $this->User;
    }

    /**
     * Get/set the base link used when generating search URLs that add a
     * search facet.If none is explicitly provided, it defaults to
     * "index.php?P=SearchResults".
     * @param string $NewValue New value to set (OPTIONAL).
     * @return string Current value.
     */
    public function baseLink(string $NewValue = null): string
    {
        if (!is_null($NewValue)) {
            $this->BaseLink = $NewValue;
        }

        return $this->BaseLink;
    }

    # ---- PRIVATE INTERFACE -------------------------------------------------

    protected $User;
    protected $SchemaId;

    ##
    # Facet generation functions

    /**
     * Generate (i.e. bring into existence) a list of search facets
     *   (i.e. suggested terms that can be added to a search) that can be
     *   later displayed. Internally, these facets are stored as modified
     *   search URLs in the SuggestionsByFieldName and
     *   TreeSuggestionsByFieldName data members. The former stores
     *   suggestions for Controlled Name and Option fields, the latter
     *   suggestions for Classification fields.
     */
    protected function generateFacets()
    {
        $Schema = new MetadataSchema($this->SchemaId);
        $Fields = $Schema->getFields(
            MetadataSchema::MDFTYPE_OPTION |
            MetadataSchema::MDFTYPE_CONTROLLEDNAME |
            MetadataSchema::MDFTYPE_TREE
        );

        $ResultFacets = SearchEngine::getResultFacets(
            $this->SearchResults,
            $this->User
        );

        foreach ($Fields as $Field) {
            if (!$Field->includeInFacetedSearch()) {
                continue;
            }

            if (!$Field->userCanView($this->User)) {
                continue;
            }

            $FieldName = $Field->name();

            $Suggestions = isset($ResultFacets[$FieldName]) ?
                $ResultFacets[$FieldName] : [];

            if (count($Suggestions)) {
                # filter suggestions
                foreach ($Suggestions as $ValueId => $ValueData) {
                    # only display fields with non-empty value
                    $NewVal = $this->filterFieldValue($Field, $ValueData["Name"]);
                    if (empty($NewVal)) {
                        unset($Suggestions[$ValueId]);
                    } else {
                        $Suggestions[$ValueId]["Name"] = $NewVal;
                    }
                }
            }

            # foreach field, generate a list of suggested facets
            # and determine if the field should be open by default
            if ($Field->type() == MetadataSchema::MDFTYPE_TREE) {
                $this->populateFacetsForTreeField($Field, $Suggestions);
            } else {
                $this->populateFacetsForNameField($Field, $Suggestions);
            }
        }
    }

    /**
     * Populate the internal data used to store search facets (i.e. suggested
     *   terms that can be added to a search) for a specified Tree field from
     *   a list of suggested Classification IDs.
     * @param MetadataField $Field Metadata field to process
     * @param array $Suggestions Search suggestions from SearchEngine::getResultFacets()
     */
    private function populateFacetsForTreeField(
        MetadataField $Field,
        array $Suggestions
    ) {
        # build up a nested array of suggestions where each level of the array
        # is keyed by the termid
        $Facets = $this->convertSuggestionsToNestedArray($Suggestions);

        # if this field should always show top-level classifications, add those
        if (!$Field->facetsShowOnlyTermsUsedInResults()) {
            $Facets = $this->addTopLevelClassifications($Facets, $Field);
        }

        # get current selections
        $CurrentValues = $this->normalizeTreeValues(
            $this->SearchParams->getSearchStringsForField($Field)
        );

        # and add them to our nested array of suggestions
        $Facets = $this->addSelectionsToNestedArray(
            $Facets,
            $Field,
            $CurrentValues
        );

        # prune each branch of the tree down to the highest level that should
        # be shown (root terms and children of selected terms)
        $Facets = $this->pruneChildrenOfUnselectedFacets($Facets);

        # if necessary, add child classifications
        if (!$Field->facetsShowOnlyTermsUsedInResults()) {
            $Facets = $this->addChildrenOfSelectedTerms($Facets, $Field);
        }

        # determine how many facets we're about to suggest
        $FacetCount = $this->countFacets($Facets);

        # if there are too many suggestions, reduce to just the selected terms
        if ($FacetCount > $this->MaxFacetsPerField) {
            $Facets = $this->pruneUnselectedFacets($Facets);
        }

        # if no facets remain, nothing to do
        if (count($Facets) == 0) {
            return;
        }

        # append Add/Remove links, normalize names, and sort facets
        $this->prepareFacetsForDisplay($Facets, $Field);

        $this->TreeSuggestionsByFieldName[$Field->name()] = $Facets;
        if (count($CurrentValues) > 0) {
            $this->FieldsOpenByDefault[$Field->name()] = true;
        }
    }

    /**
     * Populate the internal data used to store search facets (i.e. suggested
     *   terms that can be added to a search) for a specified Controlled Name
     *   or Option field from a list of suggested Controlled Name IDs.
     * @param MetadataField $Field Metadata field to process
     * @param array $Suggestions Search suggestions from
     *   SearchEngine::getResultFacets()
     */
    private function populateFacetsForNameField(
        MetadataField $Field,
        array $Suggestions
    ) {
        # retrieve current search parameter values for field
        $CurrentValues = $this->SearchParams->getSearchStringsForField($Field);

        # if a field is required, and we have only one suggestion and
        # there is no current value, then we don't want to display this
        # facet because the search results will be identical
        if (($Field->optional() == false) && (count($Suggestions) == 1) &&
            !count($CurrentValues)) {
            return;
        }

        $Facets = [];

        # populate facets with terms derived from the search results
        foreach ($Suggestions as $TermId => $TermData) {
            $Facets[$TermId]["TermInfo"] = $TermData;
        }

        # add other terms if needed
        if (!$Field->facetsShowOnlyTermsUsedInResults()) {
            $Facets = $this->addFacetsFromCName($Facets, $Field);
        }

        # mark facets for terms included in the current search as selected
        $Facets = $this->markSearchTermsSelectedForCNameFacet(
            $Facets,
            $Field,
            $CurrentValues
        );

        # remove facets for terms that are not associated with any resources
        # the user can see; these are useless as search suggestions because
        # adding them to an OR search will do nothing at all and adding them
        # to an AND search will produce no results
        $Facets = $this->pruneUselessCNamesFromFacet(
            $Facets,
            $Field
        );

        # determine how many facets we're about to suggest
        $FacetCount = $this->countFacets($Facets);

        # if there are too many suggestions, reduce to just the selected terms
        if ($FacetCount > $this->MaxFacetsPerField) {
            $Facets = $this->pruneUnselectedFacets($Facets);
        }

        # if no facets remain, nothing to do
        if (count($Facets) == 0) {
            return;
        }

        # append Add/Remove links and sort
        $this->prepareFacetsForDisplay($Facets, $Field);

        $this->SuggestionsByFieldName[$Field->name()] = $Facets;
        if (count($CurrentValues) > 0) {
            $this->FieldsOpenByDefault[$Field->name()] = true;
        }
    }

    ##
    # Functions to manipulate search suggestions in nested array format.
    #
    # The format used is:
    # [
    #    TermId => [
    #        "TermInfo" => [...],
    #        ChildId => [...],
    #        ChildId => [...],
    #...
    #    ],
    #    TermId => [...],
    #...
    # ]
    #
    # Each array keyed by a ChildId recursively uses the same structure.The
    # "TermInfo" item is supplied by searchEngine::getResultFacets() and
    # starts off with keys "Id", "Name", and "Count" where the Count gives
    # the number of items in the SearchResults that have the given term
    # (i.e.the number we'd get by ANDing that term in to the current
    # search). Before display, we'll also be adding keys IsSelected (bool)
    # and one of AddLink or RemoveLink.

    /**
     * Convert a flat list of search suggestions to nested array format.
     * @param array $Suggestions Suggested search terms.
     * @return array nested array of suggestions.
     */
    private function convertSuggestionsToNestedArray(array $Suggestions): array
    {
        # build up a nested array of suggestions where each level of the array
        # is keyed by the termid
        $Facets = [];

        # pre-load our ancestor cache
        $this->AncestorCache = ClassificationFactory::getAncestorMap(
            array_keys($Suggestions)
        );

        # iterate over the suggestions, adding each to our nested array
        foreach ($Suggestions as $TermId => $TermInfo) {
            $TargetLocation = &$Facets;
            foreach ($this->getAncestorList($TermId) as $Id) {
                $TargetLocation = &$TargetLocation[$Id];
            }

            $TargetLocation[$TermId]["TermInfo"] = $TermInfo;
        }

        return $Facets;
    }

    /**
     * Add the current search terms for a field in to a nested array of
     *   search suggestions if they were absent and mark these terms selected.
     * @param array $Facets Nested array of search suggestions that will be
     *   modified.
     * @param MetadataField $Field Field we are suggesting terms for.
     * @param array $CurrentValues Current list of search strings.
     */
    private function addSelectionsToNestedArray(
        array $Facets,
        MetadataField $Field,
        array $CurrentValues
    ): array {
        # mark each level of the tree for the current selections as selected
        foreach ($CurrentValues as $SelectedValue) {
            $TargetLocation = &$Facets;

            # strip enclosing quotes
            if (preg_match('%^\"(.*)\"$%', $SelectedValue, $Matches)) {
                 $SelectedValue = $Matches[1];
            }

            $CurrentTerm = "";
            $Segments = explode(" -- ", $SelectedValue);
            foreach ($Segments as $Segment) {
                $CurrentTerm .= (strlen($CurrentTerm) ? " -- " : "").$Segment;

                $TermId = $Field->getFactory()->getItemIdByName($CurrentTerm);

                # if term is not valid, nothing to do
                if ($TermId === false) {
                    break;
                }

                # add this classification to our facets if it was absent
                if (!isset($TargetLocation[$TermId])) {
                    $Classification = new Classification($TermId);
                    $TargetLocation[$TermId] = [
                        "TermInfo" => [
                            "Id" => $Classification->id(),
                            "Name" => $Classification->name(),
                            "Count" => 0,
                        ]
                    ];
                }

                $TargetLocation = &$TargetLocation[$TermId];

                $TargetLocation["TermInfo"]["IsSelected"] = true;
            }
        }

        return $Facets;
    }

    /**
     * Add all top-level classifications for a given tree field to the list of
     *   facets.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to use
     * @return array updated facets
     */
    private function addTopLevelClassifications(
        array $Facets,
        MetadataField $Field
    ): array {
        $ClassIds = $Field->getFactory()->getItemIds(
            "Depth = 0 AND FullResourceCount > 0"
        );

        foreach ($ClassIds as $Id) {
            if (isset($Facets[$Id])) {
                continue;
            }

            $Facets[$Id] = [
                "TermInfo" => [
                    "Id" => $Id,
                    "Name" => (new Classification($Id))->name(),
                    "Count" => 0,
                ],
            ];
        }
        return $Facets;
    }

    /**
     * Add to a given list of facets any children of selected terms.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field to use
     * @erutn array updated facets
     */
    private function addChildrenOfSelectedTerms(
        array $Facets,
        MetadataField $Field
    ): array {
        foreach ($Facets as $TermId => &$SubFacets) {
            # nothing to do for terminfo entries
            if ($TermId == "TermInfo") {
                continue;
            }

            # nothing to do for non-selected terms
            if (!isset($SubFacets["TermInfo"]["IsSelected"])) {
                continue;
            }

            # assume we won't have any selected children
            $HasSelectedChildren = false;

            # iterate over child terms
            foreach ($Field->getFactory()->getChildIds($TermId) as $Id) {
                # if term is already present in our list of facets then we do not need to add it
                # but we will want to track if any such terms were selected
                if (isset($SubFacets[$Id])) {
                    $HasSelectedChildren |= isset($SubFacets[$Id]["TermInfo"]["IsSelcted"]);
                    continue;
                }

                # get classification
                $Classification = new Classification($Id);

                # if classification is not used on any records, nothing to do
                if ($Classification->fullResourceCount() == 0) {
                    continue;
                }

                # otherwise, add it into the list
                $SubFacets[$Id] = [
                    "TermInfo" => [
                        "Id" => $Id,
                        "Name" => $Classification->name(),
                        "Count" => 0,
                    ],
                ];
            }

            # if this set of subfacets contains a selected child, recurse into them as well
            # to add their children as needed
            if ($HasSelectedChildren) {
                $SubFacets = $this->addChildrenOfSelectedTerms(
                    $SubFacets,
                    $Field
                );
            }
        }

        return $Facets;
    }

    /**
     * Add entries for each selected term within a controlled name field.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to add terms for
     * @param array $CurrentValues Search strings for specified field
     * @return array Modified list of facets
     */
    private function markSearchTermsSelectedForCNameFacet(
        array $Facets,
        MetadataField $Field,
        array $CurrentValues
    ): array {
        # be sure that we have a facet for every selected term
        foreach ($CurrentValues as $Value) {
            # if this isn't an "is" condition, move to the next one
            if ($Value[0] !== "=") {
                continue;
            }

            # get the ControlledName object for this term
            $CName = $Field->getFactory()->getItemByName(substr($Value, 1));

            # if none was found, move to the next one
            if (is_null($CName)) {
                continue;
            }

            # if needed, add information for this term to our facets
            if (!isset($Facets[$CName->id()])) {
                $Facets[$CName->id()] = [
                    "TermInfo" => [
                        "Id" => $CName->id(),
                        "Name" => $CName->name(),
                        "Count" => 0
                    ],
                ];
            }

            # mark this term selected
            $Facets[$CName->id()]["TermInfo"]["IsSelected"] = true;
        }

        return $Facets;
    }

    /**
     * Add all the terms from a given controlled vocabulary to a list of facets.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to use
     * @return array updated facets
     */
    private function addFacetsFromCName(
        array $Facets,
        MetadataField $Field
    ): array {
        $Factory = $Field->getFactory();



        # refuse to add facets if vocabulary is too large
        if ($Factory->getItemCount() > $this->MaxFacetsPerField) {
            return [];
        }

        foreach ($Factory->getItemIds() as $Id) {
            if (isset($Facets[$Id])) {
                continue;
            }

            $Facets[$Id] = [
                "TermInfo" => [
                    "Id" => $Id,
                    "Name" => (new ControlledName($Id))->name(),
                    "Count" => 0,
                ],
            ];
        }

        return $Facets;
    }

    /**
     * Remove from a set of search facets entries for any controlled names
     *   where adding that name will reduce the results to zero or will not
     *   add any new results.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to use
     * @return array updated facets
     */
    private function pruneUselessCNamesFromFacet(
        $Facets,
        $Field
    ): array {
        $RFactory = new RecordFactory($Field->schemaId());

        foreach (array_keys($Facets) as $Id) {
            $RecordCount = ($Field->searchGroupLogic() == SearchEngine::LOGIC_AND) ?
                $Facets[$Id]["TermInfo"]["Count"] :
                $RFactory->associatedVisibleRecordCount(
                    $Id,
                    $this->User
                );

            if ($RecordCount == 0) {
                unset($Facets[$Id]);
            }
        }

        return $Facets;
    }

    /**
     * Remove children of facets that are not selected from a nested array of
     *   search suggestions.
     * @param array $Facets Facets to prune.
     * @return array pruned facet
     */
    private function pruneChildrenOfUnselectedFacets(array $Facets)
    {
        foreach ($Facets as $Id => $Item) {
            if ($Id == "TermInfo") {
                continue;
            }

            # if this item is a term that is not selected
            if (isset($Item["TermInfo"])) {
                if (!isset($Item["TermInfo"]["IsSelected"])) {
                    # reduce this facet down to just the term
                    $Facets[$Id] = [
                        "TermInfo" => $Item["TermInfo"],
                    ];
                    continue;
                }
            }

            $Facets[$Id] = $this->pruneChildrenOfUnselectedFacets($Item);
        }

        return $Facets;
    }

    /**
     * Remove any facets that are not selected in the current search
     * @param array $Facets Facets to prune
     * @return array Pruned facets
     */
    private function pruneUnselectedFacets(array $Facets): array
    {
        foreach ($Facets as $Id => $Item) {
            if ($Id == "TermInfo") {
                continue;
            }

            # if this item is an unselected term
            if (isset($Item["TermInfo"])) {
                if (!isset($Item["TermInfo"]["IsSelected"])) {
                    unset($Facets[$Id]);
                    continue;
                }
            }

            $Facets[$Id] = $this->pruneUnselectedFacets($Item);
        }

        return $Facets;
    }

    /**
     * Count the number of suggestions being made in a given set of facets
     * @param array $Facets Facets to count
     * @return int number of suggestions
     */
    private function countFacets(array $Facets): int
    {
        $Count = 0;
        foreach ($Facets as $Id => $Item) {
            if ($Id == "TermInfo") {
                if (!isset($Item["IsSelected"])) {
                    $Count++;
                }
            } else {
                $Count += $this->countFacets($Item);
            }
        }
        return $Count;
    }

    /**
     * Iterate over a nested array of search facets to prepare them for
     *   display. This will append AddLink and RemoveLink entries to each
     *   TermInfo that can be used to modify the current search by
     *   adding/removing the term, normalize the "Name" entries for display,
     *   and put terms in alphabetical order.
     * @param array $Facets Facets to annotate.
     * @pasam MetadataField $Field Field to add/remove search terms.
     */
    private function prepareFacetsForDisplay(
        array &$Facets,
        MetadataField $Field
    ) {
        foreach ($Facets as $Id => &$Item) {
            if ($Id == "TermInfo") {
                # generate the appropriate updated url
                if (isset($Item["IsSelected"])) {
                    $Item["RemoveLink"] = $this->removeTermFromSearchURL(
                        $Field,
                        $Item["Name"]
                    );
                } else {
                    $Item["AddLink"] = $this->addTermToSearchURL(
                        $Field,
                        $Item["Name"]
                    );
                }

                # set the name that should be displayed
                if ($Field->type() == MetadataSchema::MDFTYPE_TREE) {
                    $Segments = explode(" -- ", $Item["Name"]);
                    $Item["Name"] = end($Segments);
                }
            } else {
                $this->prepareFacetsForDisplay($Item, $Field);
            }
        }

        # alphabetize the facets at this level of the tree
        uasort(
            $Facets,
            function ($A, $B) {
                if (isset($A["TermInfo"]) && isset($B["TermInfo"])) {
                    return $A["TermInfo"]["Name"] <=> $B["TermInfo"]["Name"];
                } elseif (isset($A["TermInfo"]) && !isset($B["TermInfo"])) {
                    return -1;
                } elseif (!isset($A["TermInfo"]) && isset($B["TermInfo"])) {
                    return 1;
                } else {
                    return 0;
                }
            }
        );
    }

    ##
    # functions to manipulate search URLs

    /**
     * Add a specified term to our search URL.
     * @param MetadataField $Field Metadata field for this term.
     * @param string $Term Search term to add.
     * @return string URL with search parameters including new term.
     */
    private function addTermToSearchURL(
        MetadataField $Field,
        string $Term
    ): string {
        if ($Field->type() != MetadataSchema::MDFTYPE_TREE) {
            $SearchStrings = $this->SearchParams->getSearchStringsForField($Field);
            $SearchStrings[] = "=".$Term;
        } else {
            $TreeArray = $this->addTermToTreeArray(
                $this->getSearchTermsAsTreeArray($Field),
                $Term
            );

            $SearchStrings = [];
            foreach ($this->treeArrayToSearchStrings($TreeArray) as $NewTerm) {
                $SearchStrings[] = "^".$NewTerm." --";
            }
        }

        # create our own copy of search parameters
        $OurSearchParams = clone $this->SearchParams;

        # clear any current search strings for this field
        $OurSearchParams->removeParameter(null, $Field);

        # create a new subgroup with our new search strings
        $Subgroup = new SearchParameterSet();
        $Subgroup->logic($Field->searchGroupLogic());
        $Subgroup->addParameter($SearchStrings, $Field);

        # add it to our search
        $OurSearchParams->addSet($Subgroup);

        # build new URL with revised search parameters
        $Url = implode("&amp;", array_filter([
            $this->BaseLink,
            $OurSearchParams->UrlParameterString()
        ]));

        # return new URL to caller
        return $Url;
    }

    /**
     * Remove a specified term from our search URL.
     * @param MetadataField $Field Metadata field for this term
     * @param string $Term Term or array of Terms to remove
     * @return string URL with search parameters with term removed.
     */
    private function removeTermFromSearchURL(
        MetadataField $Field,
        string $Term
    ): string {
        # create our own copy of search parameters with specified parameter removed
        $OurSearchParams = clone $this->SearchParams;

        if ($Field->type() == MetadataSchema::MDFTYPE_TREE) {
            $TreeArray = $this->removeTermFromTreeArray(
                $this->getSearchTermsAsTreeArray($Field),
                $Term
            );
            $NewTerms = $this->treeArrayToSearchStrings($TreeArray);

            # clear existing settings from the url
            $OurSearchParams->removeParameter(null, $Field);
            foreach ($NewTerms as $NewTerm) {
                $OurSearchParams->addParameter(
                    "^".$NewTerm." --",
                    $Field
                );
            }
        } else {
            $OurSearchParams->removeParameter(
                "=".$Term,
                $Field
            );
        }

        # build new URL with revised search parameters
        $Url = implode("&amp;", array_filter([
            $this->BaseLink,
            $OurSearchParams->UrlParameterString()
        ]));

        # return new URL to caller
        return $Url;
    }

    ##
    # Functions to manipulate a nested array representation of a search terms
    # for a tree field.
    #
    # If the selections for a field are:
    #   Mathematics
    #   Science -- Biology
    #   Science -- Physics
    #
    # Then this will be represented as:
    # [
    #     "Mathematics" => [],
    #     "Science" => [
    #         "Biology" => [],
    #         "Physics" => [],
    #      ]
    # ]

    /**
     * Get the search terms for a given field as a nested array suitable for
     *   easy manipulation of multiple selections within a given tree.
     * @param MetadataField $Field Field to fetch terms for.
     * @return array nested array of search terms
     */
    private function getSearchTermsAsTreeArray(
        MetadataField $Field
    ): array {
        static $TreeArrays;
        if (!isset($TreeArrays[$Field->id()])) {
            $CurrentTerms = $this
                ->SearchParams
                ->getSearchStringsForField($Field);

            $TreeArray = [];
            foreach ($CurrentTerms as $CurrentTerm) {
                $TreeArray = $this->addTermToTreeArray(
                    $TreeArray,
                    preg_replace('%\^(.*) --$%', '\1', $CurrentTerm)
                );
            }

            $TreeArrays[$Field->id()] = $TreeArray;
        }

        return $TreeArrays[$Field->id()];
    }

    /**
     * Convert a nested array of terms to a list of search strings.
     * @param array $TreeArray Tree array to convert.
     * @param string $ParentPrefix Parent prefix for recursive calls (DO NOT USE).
     * @return array List of search strings.
     */
    private function treeArrayToSearchStrings(
        array $TreeArray,
        string $ParentPrefix = ""
    ): array {
        $Result = [];

        foreach ($TreeArray as $ChildPrefix => $Children) {
            if (count($Children) == 0) {
                $Result[] = (strlen($ParentPrefix) ? $ParentPrefix." -- " : "").$ChildPrefix;
            } else {
                $Leaves = $this->treeArrayToSearchStrings($Children, $ChildPrefix);
                foreach ($Leaves as $Leaf) {
                    $Result[] = (strlen($ParentPrefix) ? $ParentPrefix." -- " : "").$Leaf;
                }
            }
        }

        return $Result;
    }

    /**
     * Add new terms to the nested array representation of a tree.
     * @param array $TreeArray Array representation to modify.
     * @param string $Term New search term to add.
     * @return array Modified array.
     */
    private function addTermToTreeArray(
        array $TreeArray,
        string $Term
    ) {
        $Segments = explode(" -- ", $Term);

        $TargetLocation = &$TreeArray;
        foreach ($Segments as $Segment) {
            if (!isset($TargetLocation[$Segment])) {
                $TargetLocation[$Segment] = [];
            }
            $TargetLocation = &$TargetLocation[$Segment];
        }

        return $TreeArray;
    }

    /**
     * Remove a search term and all its children for the nested array
     *   representation of a tree.
     * @param array $TreeArray Array representation to modify.
     * @param string $Term Search term to remove.
     * @return array Modified array.
     */
    private function removeTermFromTreeArray(
        array $TreeArray,
        string $Term
    ): array {
        $Segments = explode(" -- ", $Term);

        $CurLocation = &$TreeArray;
        $TargetLocation = null;
        $TargetIndex = null;

        foreach ($Segments as $Segment) {
            # if the given term isn't actually in our tree array, then there's
            # nothing to do
            if (!isset($CurLocation[$Segment])) {
                break;
            }

            $TargetLocation = &$CurLocation;
            $TargetIndex = $Segment;
            $CurLocation = &$TargetLocation[$Segment];
        }

        if (!is_null($TargetLocation)) {
            unset($TargetLocation[$TargetIndex]);
        }

        return $TreeArray;
    }

    ##
    # Misc utility functions

    /**
     * Signal event to allow other code to modify the field value.
     * @param MetadataField $Field Metadata field to process
     * @param array|string $Value Value of the field.
     * @return mixed Possibly modified field value.
     */
    private function filterFieldValue(
        MetadataField $Field,
        $Value
    ) {
        $SignalResult = $GLOBALS["AF"]->signalEvent(
            "EVENT_FIELD_DISPLAY_FILTER",
            [
                "Field" => $Field,
                "Resource" => null,
                "Value" => $Value
            ]
        );

        return $SignalResult["Value"];
    }

    /**
     * Translate the "is or begins with" search groups used in past
     *   versions of search facets into the "^XYZ --" format.
     * @param array $Values Search values for a tree field.
     * @return array Possibly modified Values.
     */
    private function normalizeTreeValues(array $Values): array
    {
        if (count($Values) == 2 && preg_match('/^=(.*)$/', $Values[0], $FirstMatch) &&
            preg_match('/^\\^(.*) -- $/', $Values[1], $SecondMatch) &&
            $FirstMatch[1] == $SecondMatch[1]) {
            $Values = ["^".$FirstMatch[1]." --"];
        }

        foreach ($Values as &$Value) {
            if (preg_match('%\^(.+) -- ?$%', $Value, $Matches)) {
                $Value = $Matches[1];
            }
        }

        return $Values;
    }

    /**
     * Get the list of ancestor terms for a given classification ID.
     * @param int $Id Classification to look up.
     * @return array Ancestor IDs in order from the root id till the immediate
     *   parent of the provided Classification.
     */
    private function getAncestorList(int $Id): array
    {
        $Result = [];
        while (($Id = $this->getAncestor($Id)) >= 0) {
            array_unshift($Result, $Id);
        }

        return $Result;
    }

    /**
     * Get the ancestor of a given classification, using a cache for
     *   performance when generating facets.
     * @param int $Id Classification to look up.
     * @return int Parent classification id.
     */
    private function getAncestor(int $Id): int
    {
        if (!isset($this->AncestorCache[$Id])) {
            $this->AncestorCache[$Id] = (new Classification($Id))->parentId();
        }

        return $this->AncestorCache[$Id];
    }

    protected $FieldsOpenByDefault = [];
    protected $SuggestionsByFieldName = [];
    protected $TreeSuggestionsByFieldName = [];
    protected $ShowCounts = true;

    private $BaseLink;
    private $MaxFacetsPerField;
    private $SearchParams;
    private $SearchResults;
    private $AncestorCache = [];
}
